package com.frx.leetoffer.dayone;

public class FibonacciTest {

    public static void main(String[] args){
        long time1 = System.currentTimeMillis();
        int n1 = iterSolution(40);
        System.out.println(n1);
        long time2 = System.currentTimeMillis();
        System.out.println((time2 - time1) + "ms");
        int n2 = solution(40);
        System.out.println(n2);
        System.out.println((System.currentTimeMillis() - time1) + "ms");
    }

    /**
     * 迭代法
     * @param n
     * @return
     */
    public static int iterSolution(int n){

        if (n <= 0){
            return 0;
        }
        if (n  == 1 || n == 2){
            return 1;
        }
        int first = 1,second = 1,third = 0;
        for (int i=3;i<=n;i++){
            third = first + second;
            first = second;
            second = third;
        }
        return third;
    }

    public static int solution(int n){
        if (n <= 0){
            return 0;
        }
        if (n == 1 || n == 2){
            return 1;
        }
        return solution(n-1) + solution(n-2);
    }

}
